package array;

import java.util.Arrays;

/**
 * Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.
 * A pair (i, j) is fair if:
 * 0 <= i < j < n, and
 * lower <= nums[i] + nums[j] <= upper
 * <p>
 * Example 1:
 * Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6
 * Output: 6
 * Explanation: There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).
 * <p>
 * Example 2:
 * Input: nums = [1,7,9,2,5], lower = 11, upper = 11
 * Output: 1
 * Explanation: There is a single fair pair: (2,3).
 *
 * @author jishenghuang
 * @version 20250419
 */
public class CntNumFairPairs_2563 {
    /**
     * nums[i] + nums[j] == nums[j] + nums[i], the condition i < j degrades to i != j
     * We can sort the array and use two-pointer technique to count the pairs less than a certain value
     * We do it twice for upper and lower and then take the difference
     *
     * @param nums
     * @param lower
     * @param upper
     * @return
     */
    public static long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);

        return countLess(nums, upper) - countLess(nums, lower - 1);
    }

    /**
     * Helper method to count the sum of  two indices is less then val
     *
     * @param nums the given integer array
     * @param val  the given value
     * @return the number of the sum of two indices is less than val
     */
    public static long countLess(int[] nums, int val) {
        long res = 0;

        for (int i = 0, j = nums.length - 1; i < j; ++i) {
            // Decrement j until nums[i] + nums[j] <= val
            while (i < j && nums[i] + nums[j] > val) {
                --j;
            }

            res += j - i;
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 7, 4, 4, 5};
        int lower = 3;
        int upper = 6;

        System.out.println(countFairPairs(nums, lower, upper));

        nums = new int[]{1, 7, 9, 2, 5};
        lower = 11;
        upper = 11;

        System.out.println(countFairPairs(nums, lower, upper));
    }
}
